The present invention relates to a logical block for decoding a signal which is encoded by means of a convolutional code defined at the receiving end at each sampling instant by one out of N possible states. These N possible states are also referred to as a "data channel", because all N possible states at the receiving end must be evaluated and thus correspond to a predetermined data channel, so to speak. This specific encoding technique is described in detail, for example, in an article by A. J. Viterbi entitled "Convolutional Codes and Their Performance in Communication Systems", IEEE Transactions on Communications Technology, Vol. COM-19, No. S. October 1971, pages 751 to 772. A. J. Viterbi developed an efficient algorithm for carrying out maximum-likelihood detection of such convolutional codes. Such an algorithm is commonly referred to as the Viterbi algorithm or "Viterbi decoding". At the transmitting end, the redundancy of arbitrary data sequences is increased by appending additional data. Protection of the data to be transmitted or stored is not achieved by incorporating an internal redundancy, but the redundancy is selectively added to the data. This makes it possible to transmit arbitrary data sequences in protected form, whereby convolutional coding is universally applicable. One application in the consumer-electronics field is the protection of digitized audio data which are either transmitted in any form or originates from a digital storage medium which is error-prone because of its high storage capacity.
At the receiving end, a probability analysis is made over a plurality of received data words to determine which is the most likely data sequence, which then corresponds to the original information. Erroneous decoded data do not only affect a single bit of the respective data sequence, but the perturbing effect is distributed over a wide range of the data sequence. Thus, the effect on the individual data word remains relatively small, so that the decoder can reconstruct the correct, error-free contents of the original signal to make them available at its output for further processing.
The logical blocks for implementing a Viterbi decoder are very large, since not only a large range of the received and reconstructed data sequence needs to be stored, but also the data sequences that would have arisen if the currently received data words had been meant differently at the transmitting end and were misinterpreted due to errors or disturbances.
In the Viterbi decoding process, all N possible receive states are examined at each sampling instant as to how well they match the received data. This is done by comparing theoretical expected values with the received data words. Each of the N possible states is assigned a fixed digital expected value which depends on the respective Viterbi encoding technique used. The comparison between the received data words and the expected values is made using a distance or difference computation. The smaller the distance value, the higher the probability that the state currently being examined is actually assigned to the received data words. By continuously accumulating the distance values, the probability consideration is extended to the sequence of already received data words, so that the most likely sequence will, in the course of time, have the least accumulated distance value. Through this cumulative evaluation, a single error "disappears" in the sum of errors.
The continuous evaluation of the added distance values thus results in a large number of data sequences with different probabilities, which must be updated after each data clock pulse at the latest. The individual data sequence is referred to as a "path". In graphical form, cf., for example, FIGS. 5 and 7, the individual paths can be represented in a trellis diagram. The trellis diagram has a horizontal time axis with the successive sampling instants, while the vertical direction represents the N different states in a sort of row arrangement. According to the received data, the transitions from one state to the next are evaluated by determining the respective distance between expected value and received value. Since each state can be reached from at least two preceding states, a selection is made in the sense that in the case of multiple transitions, only the respective transition with the smaller or the same accumulated distance value is used. In the trellis diagram, the graphic sequence of the individual transitions represents the respective path. If the accumulated distance values are entered at the intersections of the trellis, the most likely path is readily apparent from the trellis diagram. The individual paths tend to differ initially, but for relatively old sampling instants, they merge into a single path which is obviously free from errors, i.e., which contains the sequence of original, error-free states. It can thus be assumed that the states in this range are correct, so that the original data, hereinafter also called "candidates", can be determined therefrom by inverse Viterbi coding. Thus, at each sampling instant, the most likely candidate is determined, which is added to the sequence of candidates already determined, so that the sequence of original data is restored.
This short description of the Viterbi decoding technique shows that a great number of data have to be processed, stored, and reloaded in real time, since for each of the N possible states, both the associated paths and the accumulated difference values must be determined and stored. In each cycle, besides the determination of the new distance values, of the accumulated distance values, and of the new transitions, reloading the data of all stored paths takes place. This is readily apparent from the trellis diagrams of FIGS. 5 and 7.
It is, therefore, an object of the invention to provide a logical block of reduced circuit complexity for a flexible Viterbi decoder which is suitable for incorporation into a monolithic integrated signal-processing circuit and for processing high data rates.